// Package day_09_order_table_join_search_set islands_question
// @Title day_09_order_table_join_search_set
// @Description  https://leetcode-cn.com/problems/number-of-islands/
// @Author  == 琳琳也叫王木木 ==  2021/9/2 20:02
// @Create  2021/9/2 20:02
package day_09_order_table_join_search_set

// 岛屿问题

func NumIslands(grid [][]byte) int {
	if grid == nil || grid[0] == nil {
		return 0
	}
	N := len(grid)    // 行号
	M := len(grid[0]) // 列号
	res := 0
	for i := 0; i < N; i++ {
		for j := 0; j < M; j++ {
			if grid[i][j] == '1' {
				res++
				infect(grid, i, j, N, M)
			}
		}
	}
	return res
}

func infect(m [][]byte, i, j, N, M int) {
	if i < 0 || i > N || j < 0 || j > M || m[i][j] != '1' {
		return
	}
	// i,j 没有越界，并且当前位置是1
	m[i][j] = '2'
	infect(m, i+1, j, N, M)
	infect(m, i-1, j, N, M)
	infect(m, i, j+1, N, M)
	infect(m, i, j-1, N, M)
}
